package com.company.tree;

import com.company.TreeNode;

import java.util.Stack;

/**
 * @author jrue
 * @version 1.0
 * @date 2020/1/27 20:06
 */
public class TreeOperation {
    // 前序遍历的非递归
    public void traversalWithStack(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode thisNode = stack.pop();
            System.out.print(thisNode.val + " ");
            if (thisNode.right != null) {
                stack.push(thisNode.right);
            }
            if (thisNode.left != null) {
                stack.push(thisNode.left);
            }
        }
    }

    // 前序遍历的递归
    public void traversal(TreeNode root) {

        if (root == null) return;
        System.out.print(root.val + " ");
        traversal(root.left);
        traversal(root.right);

    }

    // 中序遍历的递归
    public void traversal02 (TreeNode root) {
        if (root == null) return;
        traversal02(root.left);
        System.out.print(root.val + " ");
        traversal02(root.right);
    }

    // 中序遍历的非递归
    public void traversal02withStack (TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
             if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode thisNode = stack.pop();
                System.out.print(thisNode.val + " ");
                p = thisNode.right;
            }
        }
    }

    // 后序遍历递归
    public void traversal03 (TreeNode root) {
        if (root == null) return;

        traversal03(root.left);
        traversal03(root.right);
        System.out.print(root.val + " ");
    }

    // 后序遍历的非递归
    public void traversal03withStack (TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                if (p.right != null) {
                    stack.push(p.right);
                }
                p  = p.left;
            } else {
                TreeNode thisNode = stack.pop();
                System.out.print(thisNode.val + " ");
                p = thisNode;
            }
        }

    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        new TreeOperation().traversal02(root);
        System.out.println();
        new TreeOperation().traversal02withStack(root);
        System.out.println();
        new TreeOperation().traversal03(root);
        System.out.println();
        new TreeOperation().traversal03withStack(root);
    }
}
